package com.zdy.demo;



/**
 *   第3题
 *   一个二维数组，每一行从左到右递增，每一列从上到下递增．
 *   输入一个二维数组和一个整数，判断数组中是否含有整数
 * @author deyou
 * @version 1.0
 * @date 2021/5/19 15:23
 */

public class FindeNum03 {
    /***
     * 双指针法
     * 时间复杂度 O(mn) ,空间复杂度O(1)
     * @param array
     * @param target
     * @return
     */
    public static boolean find(int[][] array, int target){
        if(array == null || array.length == 0){
            return false;
        }
        //行y
        int row = 0;
        //列x
        int column = array[0].length-1;
        //第一个目标数和第一行。最后一个数比较
        while(row < array.length && column >= 0){
            if (array[row][column] == target){
                return true;
            }
            //如果目标值小于 最后一个值，从该行往前找
            if(array[row][column] > target){
                column--;
                //大于就从下一行查找。
            }else {
                row++;
            }
        }
        return false;
    }

    /**
     * 解法二 二分法查找
     * 时间复杂度O(log mn),空间复杂度O(1)
     * @param array
     * @param target
     * @return
     */

    public static boolean find2(int[][] array, int target){
        //判断数组非null ，或数组没有元素
        if(array == null || array.length == 0){
            return false;
        }

        int low = 0;  //低位
        int hight = array.length * array[0].length -1;//高位
        int col = array[0].length; // 每行数组长度

        //二分法查找
        while(low <= hight){
            int mid = (low + hight)/2;
            int midValue = array[mid/2][mid%2];
            if(midValue == target){
                return true;
            }
            if (midValue> target){
                low = mid + 1;
            }else {
                hight = mid - 1;
            }
        }
        return false;

    }

}


